package pilgun.Multithread.MergeSort;

class PMerge implements Runnable{
	private int[] T;
	private int[] A;
	private int p1, p2, p3;
	private int r1, r2;
	
	
	public PMerge(int[] t, int p1, int r1, int p2, int r2, int[] a, int p3) {
		A = a;
		T = t;
		this.p1 = p1;
		this.p2 = p2;
		this.p3 = p3;
		this.r1 = r1;
		this.r2 = r2;
	}

	public int binarySearch(int x, int[] T, int p, int r){
		int low = p;
		int high = Math.max(p, r+1);
		int mid;
		while (low<high){
			mid = (low+high)/2;
			if (x<=T[mid]){
				high = mid;
			}
			else
				low = mid+1;
		}
		return high;
	}
	
	public void run(){
		   int n1 = r1 - p1 + 1;
		   int n2 = r2 - p2 + 1;
		   int t;
		   int q1, q2, q3;
		   if (n1<n2){
			   //swap if necessary
			   t = n1;
			   n1 = n2;
			   n2 = t;
			   t = p1;
			   p1 = p2;
			   p2 = t;
			   t = r1;
			   r1 = r2;
			   r2 = t;
		   }
		   if (n1 == 0){
			   return;
		   }
		   else{
			   q1 = (p1+r1)/2;
			   q2 = binarySearch(T[q1], T, p2, r2);
			   q3 = p3+(q1-p1)+(q2-p2);
			   A[q3] = T[q1];
			   PMerge pMerge1 = new PMerge(T, p1, q1-1, p2, q2-1, A, p3);
			   PMerge pMerge2 = new PMerge(T, q1+1, r1, q2, r2, A, q3+1);
			   Thread first = new Thread(pMerge1);
			   first.start();
			   pMerge2.run();
			   try {
				   first.join();
			   } catch (InterruptedException e) {
				e.printStackTrace();
			   }
		   }
	}
}
